package 左哥算法.ch01异或运算;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Ch02位图 {
    /**
     * ch01：找到数组中消失的数字
     * 其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，以集合的形式返回结果。
     */
    @Test
    public void test(){
        findDisappearedNumbers(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,
        13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,29,29,32,35}).forEach(
                n->{
                    System.out.printf(n+"，");
                }
        );
//        findDisappearedNumbers(new int[]{13,98,15,75,16,49,25,10,62,1,8,49,7,25,79,67,81,93,62,
//                83,61,46,17,50,29,27,3,24,41,35,69,34,28,12,18,46,72,64,2,64,11,17,48,52,95,89,
//                19,40,83,24,82,32,84,88,66,39,54,61,36,9,30,88,16,52,81,80,22,37,44,85,35,60,22,
//                70,34,54,63,8,60,92,2,20,40,50,96,70,10,98,66,51,6,65,97,67,57,9,27,82,63,59}).forEach(
//                n->{
//                    System.out.printf(n+"，");
//                }
//        );
    }

    /**
     * ch01：
     *  思路：
     *      1.创建一个length/32+1的int类型数组，用于存储出现的数字。（需要将无效位做预处理）
     *      2.遍历数组，当某一个数字出现时，将该数字n，放入nums[n/32]的二进制第 n%32位，（如果超过了数组范围则不放入）
     *          (放入位图：1<<n%32||nums[n/32])
     *      3.遍历位图，找到位图中所有为0的位置，直到将其放入集合中（该数=第i位+数组下标*32），直到遍历到最后一位有效位置
     *          如何找到最右侧0的位置，将(num+1)&(~num)，在对其进行Math.lg(n)/Math.lg(2)
     *          找到后|上原数据再次寻找最右的0位置
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list=new ArrayList<>();
        int range=32;
        int[] bitmap=new int[nums.length/range+1];
        bitmap[bitmap.length-1]=(~0)<<(nums.length%range+1);    //将无效位填充1
        for (int num : nums) {
            int index=num/range;
            if (index<bitmap.length){
                bitmap[index]=1<<num%range | bitmap[index];  //将每个数放入位图中
            }
        }
        for (int i = 0; i < bitmap.length; i++) {
            long rightZero=rightZero=(bitmap[i]+1)&(~bitmap[i]);
            int noShow=(int)(i*range+Math.log(rightZero)/Math.log(2));
            //当该位图并非所有位置都为0，且该位置没有超过最后一位
            while (bitmap[i]!=0xFFFF_FFFF){
                rightZero=((long)bitmap[i]+1)&(~bitmap[i]);
                noShow=(int)(i*range+Math.log(rightZero)/Math.log(2));
                list.add(noShow);
                bitmap[i]=bitmap[i]+(int)rightZero;
            }
        }
        list.remove(0);
        return list;
    }

}
